package sort;

/**
 * Created with IntelliJ IDEA.
 * Description:快速排序
 * 取某元素素作为基准值，分割成两子系列，左右重复分割
 * User: 张宇田
 * Date: 2025-04-14
 * Time: 13:20
 */
public class Sort {
    //left = 0 ; right = arr.length - 1;
    //这个是基于Hoare方法
    public static void quickSort(int[] arr,int left,int right){
        if (left>=right){
            return;
        }

        int div = partition2(arr,left,right);

        quickSort(arr,left,div-1);
        quickSort(arr,div+1,right);

    }

    private static int partition(int[] arr,int l,int r){
        int pivot = arr[l];
        int index = l;
        while(l < r){
            //此处会越界 1 2 3 4 5 6 r一直--，
            while((l < r) &&arr[r] >= pivot){
                r--;
            }


            while ((l < r) &&arr[l] <= pivot){
                l++;
            }
            swap(arr,l,r);
        }
        swap(arr,index,l);
        return l;
    }

    private static void swap(int[] arr,int left,int right){
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }

    private static int partition2(int[] arr,int l,int r){
        int pivot = arr[l];
        while(l<r){
            while(l<r && arr[r]>=pivot){
                r--;
            }
            arr[l] = arr[r];
            while(l<r && arr[r]<=pivot){
                l++;
            }
            arr[r] = arr[l];
        }
        //相遇之后，把pivot的值放到相应的下标处
        arr[l] = pivot;
        return l;
    }



}


